1. Field of the Invention
The present invention pertains to image processing systems. More particularly, this invention relates to an image processing system with (1) skew correction that does not require human intervention or the presence of text or skew detection information on the original document, and (2) image cropping that is done regardless of the shape of the image.
2. Description of the Related Art
It has been known that when a document (i.e., the original physical object, such as photo or text document) is scanned by a scanner, a digital image of the original document is typically generated. The digital image of the original document is, however, often found to be skewed (rotated) inside the entire scan image (i.e., inside the entire digital image obtained from the scanner). As is known, the scan image typically includes the image of the document as well as background information. A skew or inclination of the document image within the scan image is particularly likely to occur when the scanner uses an automatic document feed mechanism to feed the original document for scanning. In addition, when the size of the original document is relatively small in comparison to the scan region of the scanner, the scan image may contain considerable amount of background information.
For instance, some scanning devices are automatic sheet fed scanners with stationery charge coupled devices (CCD""s). These scanning devices feed the document past the CCD for scanning. The document must be grabbed by a set of rollers for scanning. This mechanism can sometimes scratch the document. Also, small documents may not be securely grabbed or reliably sensed by the mechanism. In addition, only a single document at a time can be fed in the scanner. As a result, document carriers are used to overcome these problems. A document carrier is usually a transparent envelope having a white backdrop. The document or documents of interest are inserted within the envelope for scanning. The document carrier protects the scanned document from scratches and also provides the rollers with a larger width original to grab, thereby accomplishing successful feeding of the document through the scanner.
However, one disadvantage of using a document carrier is that the document carrier also becomes part of the scanned data. For example, if the carrier color does not exactly match the color of the scanner background, edges of the document carrier will be contained in the scanned data. This spurious data will cause the digital image to contain unwanted extraneous information. FIG. 1 illustrates a scan image 100 that exhibits these problems.
As can be seen from FIG. 1, the scan image 100 contains a document image 110 of an original document. The remaining area of the scan image 100 is background 120, which typically has a predetermined pixel pattern, and extraneous information 140, which typically has known characteristics. The background 120 can be caused by the scanner background while the extraneous information 140 can be caused by a document carrier. The document image 110 is skewed inside the scan image 100 and the background 120 is a considerable fraction of the scan image 100. When the scan image 100 is displayed on a display or printed by a printer, the document image 110 typically has a relatively unpleasant and poor visual quality. In addition, the skewed image may also cause errors when the image data is further processed by other software programs, such as optical character recognition programs.
Techniques have been developed to try to detect and correct the skew problem. For example, U.S. Pat. No. 4,941,189, entitled OPTICAL CHARACTER READER WITH SKEW RECOGNITION and issued on Jul. 10,1990, describes a skew correction technique that searches for text characters along a scan line. As another example, U.S. Pat. No. 5,452,374, entitled SKEW DETECTION AND CORRECTION OF A DOCUMENT IMAGE REPRESENTATION and issued on Sep. 19, 1995, describes another technique that segments the scan image into text and non-text regions and then determines the skew information based on the resulting segmentation.
These techniques, however, require the original document to contain at least some text. The techniques then rely on the detection of one or more lines of the text in the document. With the advent of inexpensive photo scanners and multimedia personal computers, scanners are nowadays used to scan not only text documents, but photographs and other image documents as well. The photographs, however, typically do not contain any text data. This thus causes the skew detection and correction techniques to be inapplicable to the scanned photo images. In addition, because photographs can have a variety of sizes and shapes, it is typically difficult to trim the background information from the scanned image of a photograph.
Another technique has been proposed that detects the skew information of a scanned image without requiring the presence of text in the scanned document. One such technique is described in U.S. Pat. No. 5,093,653, entitled IMAGE PROCESSING SYSTEM HAVING SKEW CORRECTION MEANS, and issued on Mar. 3, 1992. However, this technique requires human intervention.
Described below is a system and method for automatically determining in a scanned document image the presence of unwanted extraneous information caused by an extraneous device, for example, a document carrier and scanner background information. Once the presence of this information is determined, the system and method of the present invention can compute, for instance, skew and crop statistics. From this, the image can be automatically deskewed and cropped appropriately without the background and extraneous information (such as marks from the document carrier). The system and method accomplishes this by first determining the presence of unwanted extraneous and background information and then appropriately processing the document image. The extraneous information is ignored during deskew and crop computations. Also, the scanner background and the extraneous information are prevented from being included with the final digital representation of the image.
Specifically, scanner background information and any extraneous information, such as edges created by the document carrier, are ignored when processing information is computed, such as skew and crop statistics, while image edges are retained, such as document edges of an image or text pages. Thus, the system and method of the present invention optimizes automatic cropping and deskewing results of document images scanned by general purpose scanning devices that are used with or without document carriers.
Also, the system and method described below determines a skew angle of the document image without requiring text in the document or human intervention. This feature is accomplished by determining an edge of the document image within a scan image and using that edge to determine the skew angle of the document image. The edge can be determined by locating the first or last document image pixel of each scan line of pixels in the scan image that belongs to the document image (i.e., the edge pixel of the document image along that scan line). This is accomplished by comparing a scan line of pixels with a predetermined scan line of background pixels or alternatively by comparing a neighborhood around a scan line with predetermined background pixels. The skew angle of the document image is then determined by computing the slope of the detected edge in the scan image.
In addition, the system and method described below can determine the boundary of the document image. This feature is accomplished by locating (1) a first document image pixel and a last document image pixel for a first scan line of the document image in the scan image, (2) a first document image pixel and a last document image pixel of a last scan line of the document image in the scan image, (3) a leftmost document image pixel of the document image in the scan image, and (4) a rightmost document image pixel of the document image in the scan image.